package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class Code40 {
	
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	Arrays.sort(candidates);
    	
//    	Map<Integer,List<List<Integer>>> map=new HashMap<Integer,List<List<Integer>>>();
    	int n=candidates.length;
    	int m=1<<n;
    	int i,j;
    	Set<String> vis=new HashSet<String>();
    	for(i=0;i<m;i++){
    		int sum=0;
    		List<Integer> list=new ArrayList<Integer>();
    		StringBuilder sb=new StringBuilder();
    		for(j=0;j<n;j++){
    			if((i&(1<<j))>0){
    				sum+=candidates[j];
    				list.add(candidates[j]);
    				sb.append(","+candidates[j]);
    			}
    			if(sum>=target)
    				break;
    		}
    		if(sum==target && !vis.contains(sb.toString())){
    			result.add(list);
    			vis.add(sb.toString());
    		}
    	}
    	
    	return result;
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	Arrays.sort(candidates);
    	int n=candidates.length;
    	if(n==0)
    		return result;
    	Stack<Integer> stack=new Stack<Integer>();
    	dfs(0,0,target,candidates,n,stack,result);
    	return result;
    }
    
    public void dfs(int start,int sum,int target,
    		int[] nums,int n,
    		Stack<Integer> stack,
    		List<List<Integer>> result){
    	
    	if(sum>target || start>n)	return ;
    	if(sum==target){
    		result.add(new ArrayList(stack));
    		return ;
    	}
    	for(int i=start;i<n;){
    		stack.push(nums[i]);
    		dfs(i+1,sum+nums[i],target,nums,n,stack,result);
    		stack.pop();
    		int j=i+1;
    		while(j<n && nums[j]==nums[i])
    			j++;
    		i=j;
    	}
    }
    public static void main(String[] args){
    	int[] nums={10,1,1,2,7,6,5};
    	Code40 code=new Code40();
    	code.combinationSum2(nums, 8);
    }
}
